// https://www.lintcode.com/problem/sqrtx/

public class Solution {
    /**
     * @param x: An integer
     * @return: The sqrt of x
     */
    public int sqrt(int x) {
        // write your code here
        if (x <= 1) {
            return x;
        }
        return _sqrt(x, 0, x);
    }
    
    private int _sqrt(int x, int start, int end) {
        int mid = (start + end) / 2;
        long square = (long)mid * (long)mid; // 小心溢出...
        if (square == x) {
            return mid;
        }
        else {
            if (mid == start) {
                return start;
            }
            if (square < x) {
                return _sqrt(x, mid, end);
            }
            else {
                return _sqrt(x, start, mid);
            }
        }
    }
}